Method 1: updateNetwork |
Input: Graph G, edge changed e, ε, µ |
u, v = nodes of e for x in (u, v): if x == u: x’ = v else: x’ = u if x is a core: propagateId(x, generateNewId(), ε, µ) if e was a removal: if x’ is not density connected from x and id(x’) == id(x): if x’ is a core: propagateId(x’, generateNewId(), ε, µ) else: makeHubOrOutlier(x’) else: if x was a core: for nei in neighborhood of x: if id(nei) == id(x) and nei has not been changed: propagateId(x’, generateNewId(), ε, µ) if x was not changed: makeHubOrOutlier(x) for nei in neighborhood of x: if nei is not a core and does not neighbor a core: makeHubOrOutlier(nei) |
Method 2: propagateId |
Input: Vertex v, id, ε, µ |
if v is a core: push v onto the queue while |queue| > 0: u = pop from top of queue if u was not checked already: id(u) = id if u is a core: push all ε-neighbors of u to the queue |